//437 Path Sum
/*
给定一个整数二叉树，其每个结点都存放一个整数值，求有多少条路径节点值的和等于给定值
即输入一个二叉树和一个给定整数，输出一个整数，表示有多少条满足条件的路径。

Input: sum = 8, tree =
		 10
	    /  \
	   5   -3
	  / \    \
	 3   2   11
	/ \   \
   3  -2   1
Output: 3  和为 8 的路径一共有三个：[[5,3],[5,2,1],[-3,11]]。


*/
// 主函数
int pathSum(TreeNode *root, int sum)
{
	//pathSumStartWithRoot(root, sum) 处理根结点开始的情况
	// 
	return root ? pathSumStartWithRoot(root, sum) +
					  pathSum(root->left, sum) + pathSum(root->right, sum)
				: 0;
}


// 辅函数
int pathSumStartWithRoot(TreeNode *root, int sum)
{
	//
	if (!root)
	{
		return 0;
	}

	//
	int count = root->val == sum ? 1 : 0; 

	//根的左右结点情况处理
	count += pathSumStartWithRoot(root->left, sum - root->val);
	count += pathSumStartWithRoot(root->right, sum - root->val);
	return count;
}